package 单调栈;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/2/14 21:07
 */
public class zuo子数组和积问题 {
    /*
    给定 一个 只包含 整数的 数组, arr , arr 种任何一个子数组 一定 可以算出 (sub子数组的累加和) * (sub 种最小值)  的值, 成为 指标 A,
    那么 在所有的子数组 种,指标 A 的 最大是多少?

    ---:
      我们 直接 从结果 考虑: 最优的 指标 A 的值  一定 是 A = sum(i,j) * min(i,j)
      首先 要明白的 一个点: sum(i,j) 一定是 arr 的一个 区间和 ,而  min 值 一定是 数组种 某一个 值:
      从整体 来看的 话, 不容易 考虑 A 的单调性, 所以
      这种 固定 一个值, 去 判断另外一个值 变化的 这种思想 才是 关键!

      --
      而我们 去 空值区间和 不变 去分析 min 的话, 也不太 好分析,
      但是 我们 去枚举 控制 min 的值 来 分析 区间和 ,这种 单调性 是可以  看出来的!
      --
      以 arr[i] 作为 区间的 最小值, 求 以 arr[i] 为区间最小值 时, 区间和 最大 ,那么 指标 A, 就最大!
      求 以 x 为最小值 的最大区间和, 这不就单调栈的 领域嘛! ( 既能保证 x 是 区间 最小, 又能 保证 x 所在的 区间和 是最大的! )


      -- 这样就可以用到 单调栈了!
     */



    public int solution(int[] nums){
        int max = 0;
        int preSum[] = new int[nums.length + 1];
        for(int i = 0;i < nums.length;i++){
            preSum[i + 1] =  preSum[i] + nums[i];
        }
        /*
          有点 抽象的!
          说实话!
          好像 有点不对!
         */
        int index[][] = repeatElementVersion(nums);
        for(int i = 0;i < nums.length;i++){
            max = Math.max(max,nums[i] * (preSum[index[i][1]] - preSum[index[i][0] + 1]));
        }
        return max;
    }

    public int[][] repeatElementVersion(int[] nums) {
        int ans[][] = new int[nums.length][2];
        Deque<Deque<Integer>> stack = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peekLast().peekLast()]) {
                Deque<Integer> integers = stack.pollLast();
                int lfetIndex = stack.isEmpty() ? -1 : stack.peekLast().peekLast();
                while(!integers.isEmpty()){
                    int temp = integers.pollLast();
                    ans[temp][0] = lfetIndex;
                    ans[temp][1] = i;
                }
            }

            if (stack.isEmpty() || nums[i] > nums[stack.peekLast().peekLast()]) {
                stack.offerLast(new ArrayDeque<>());
                stack.peekLast().offerLast(i);
            } else {
                stack.peekLast().offerLast(i);
            }
        }
        while(!stack.isEmpty()){
            Deque<Integer> integers = stack.pollLast();
            while(!integers.isEmpty()){
                int temp = integers.pollLast();
                ans[temp][1] = -1;
                ans[temp][0] = stack.isEmpty() ? -1 : stack.peekLast().peekLast();
            }
        }

        return ans;
    }


}
